"""
将算式转变为二叉树结构,并计算
"""
import math
from .binary_tree import BinaryNode

def parse_formula_to_list(formula:str)->list:
    """
    将算式转换成列表
    例如:
    ((11+22)*33 - (-533))/6 + 12
    返回:
    [ '(', '(','11','+','22',')','*','33','(','-','533',')',')','/','6','+','12']
    """
    result = []
    number = ''
    operator = ['+','-','*','/','(',')']
    digit = [str(i) for i in range(10)]
    for i,c in enumerate(formula):
        if c in operator:
            if number:
                result.append(number)
                number = ''
            result.append(c)
        elif c in digit or c == '.':
            number += c
    if number:
        result.append(number)
    #对 (- 组合当负数解释
    result2 = []
    skip = 0
    for u,v in enumerate(result):
        if skip > 0:
            skip -= 1
        elif u+3<len(result) and result[u] == '(' and result[u+1] == '-' and result[u+3]==')':
            result2.append(result[u+1]+result[u+2])
            skip = 3
        else:
            result2.append(v)
    return result2

def is_number(ts)->bool:
    '''
    判断传入值是否为数字
    '''
    try:
        float(ts)
    except ValueError or TypeError:
        return False
    return True

def check_formula_list(flist:list):
    """
    初步检查公式是否符合规范
    1.括号一一对应
    2.操作符两端连接正确,操作符两端可以是数字,或者括号和反括号 !1+2, !1+(,!)+(,...
    3.数字符合规范
    通过返回True,'',失败返回False ,失败打印原因
    """
    #括号检测
    if len(flist) == 0:
        return True,''
    s = 0
    for i,v in enumerate(flist):
        if v == '(':
            s += 1
        elif v == ')':
            s -= 1
        if s < 0:
            return False,"括号类型错误"
    if s != 0:
        return False,'括号不匹配'
    
    #数匹配
    operator = ['+','-','*','/','(',')']
    for i,v in enumerate(flist):
        if v not in operator:
            if not is_number(v):
                return False,'数字错误'
            
    #操作符匹配
    formula = ['+','-','*','/']
    wrong_end = ['(','+','-','*','/']
    wrong_start = [')','+','-','*','/']
    if flist[-1] in wrong_end:
        return False,'结尾错误'
    elif flist[0] in wrong_start:
        return False,'开头错误'
    for i,v in enumerate(flist):
        if v in formula and i > 0 and i < len(flist)-1:
            if (not((flist[i-1] == ')' and flist[i+1] == '(') or
                (is_number(flist[i-1]) and is_number(flist[i+1])) or
                (is_number(flist[i-1]) and flist[i+1] == '(' ) or
                (flist[i-1] == ')' and is_number(flist[i+1])))):
                return False,'操作符匹配错误'
    return True,''

def simple_flist_to_calctree(flist:list,level=0)->BinaryNode:
    """
    不含括号的简单公式列表转换为计算二叉树
    例如:  1 + 3*2 - 4
             -
           /   \
          +     4
        /   \
       1     *
            / \
           3   2
    叶节点可以是数字或者一个列表
    level = 0 表示+,-
    level = 1 表示*,/           
    """
    if len(flist)==1:
        return flist[0]
    ops = (('+','-'),('*','/'))
    last_node = None
    bi = 0
    for i,v in enumerate(flist):
        if v in ops[level]:
            if last_node  is None:
                last_node = simple_flist_to_calctree(flist[:i],1) if level==0 else flist[i-1]
            else:
                last_node = BinaryNode(operator,last_node,simple_flist_to_calctree(flist[bi:i],1) if level==0 else flist[i-1])
            operator = v
            bi = i+1
    if last_node is None:
        return simple_flist_to_calctree(flist,1)
    else:        
        return BinaryNode(operator,last_node,simple_flist_to_calctree(flist[bi:],1) if level==0 else flist[-1])

def flist_to_binarytree(flist:list)->BinaryNode:
    """
    将公式列表消除括号并转为一个二叉树结构
    例如:1+2*((1+3)*2 + 5*(3+1))
                +
             /     \
             *      *
            / \    /  \
          1+3  2  5   3+1
    """
    a = 0
    bi = 0
    clist = []
    for i,v in enumerate(flist):
        if v == '(':
            a += 1
            if a==1:
                bi = i
        elif v == ')':
            a -= 1
            if a==0:
                clist.append(flist_to_binarytree(flist[bi+1:i]))
        elif a==0:
            clist.append(v)
    return simple_flist_to_calctree(clist)

def flist_to_binarytree2(flist:list)->BinaryNode:
    """
    非递归算法
    """
    clist = []
    stack = []
    for i,v in enumerate(flist):
        if v == '(':
            stack.append(clist)
            clist = []
        elif v == ')':
            node = simple_flist_to_calctree(clist)
            clist = stack.pop()
            clist.append(node)
        else:        
            clist.append(v)
    return simple_flist_to_calctree(clist)


def get_node_value(node):
    if isinstance(node,BinaryNode):
        return node.result
    else:
        return float(node)

def calc_calctree(ftree:BinaryNode)->float:
    """
    计算二叉树ftree的值
    """
    for node in ftree:
        if node.value == '+':
            node.result = get_node_value(node.left) + get_node_value(node.right)
        elif node.value == '-':
            node.result = get_node_value(node.left) - get_node_value(node.right)
        elif node.value == '*':
            node.result = get_node_value(node.left) * get_node_value(node.right)
        elif node.value == '/':
            if get_node_value(node.right) == 0:
                return math.nan
            node.result = get_node_value(node.left) / get_node_value(node.right)
    return ftree.result

def calctree_to_formula(node:BinaryNode)->str:
    """
    二叉树转化成字符串公式
    """
    
    return node.result
